
//503.下一个更大元素II

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        //进行两次单调栈
        int n=nums.size();
        stack<pair<int,int>> st;  //从前往后,存储还没有找到满足条件的位置
        st.push({nums[0],0});
        vector<int> ret(n,-1);

        for(int i=1;i<2*n;i++)
        {
            while(!st.empty()&&st.top().first<nums[i%n])  //将找到满足条件的位置出栈
            {
                int index=st.top().second%n;
                ret[index]=nums[i%n];
                st.pop();
            }

            st.push({nums[i%n],i%n});
        }
        return ret;
    }
};